package tree.structure.treetype;

import java.util.*;

/**
 * @user 26233
 * @create 2020-04-20 22:09:40
 * @description
 *      B-树,B树
 *      多路平衡BST
 *      每个节点有最大元素数量限制 m-1，m为树的阶，表示节点最大的分支数量
 *      所有叶子节点的深度相同，如何保证的：插入节点时的节点分裂和删除节点时的树调整
 *      树的高度增加来自底层节点的向上分裂，并且每次分裂的开始是从叶节点开始，因为新添加的数据会一直下沉
 **/

class BTreeNode {
    // 阶数
    int m;
    // 父节点
    public BTreeNode parent;
    // 数据域
    // 0 < data.length < m
    List<Object> data;
    // 指针域
    // point.length = m
    List<BTreeNode> point;

    BTreeNode(int m) {
        this.m = m;
        data = new ArrayList<>(m);
        point = new ArrayList<>(m);
        parent = null;
    }
}

public class BTree<T extends Comparable> {
    // 树的阶数
    static int m = 3;
    public BTreeNode init(T[] t){
        BTreeNode root = new BTreeNode(m);
        for(int i = 0; i < t.length; i++){
            root = insert(root, t[i]);
        }
        return root;
    }
    // 插入数据
    public BTreeNode insert(BTreeNode root, T t){
        // 元素个数少于m，直接插入
        int index = 0;
        while(root != null){
            index = 0;
            // 确定元素插入位置
            for(int i = 0; i < root.data.size(); i++){
                if(t.compareTo(root.data.get(i)) > 0){
                    index = i + 1;
                }
            }
            // 元素下沉
            if(root.point.size() > index && root.point.get(index) != null){
                root = root.point.get(index);
            }else{// 没有子节点，即叶节点
                break;
            }
        }
        // 树的高度增加来自底层节点的向上分裂，并且每次分裂的开始是从叶节点开始
        // 插入到节点数组中
        root.data.add(index, t);
        // 检查该节点是否需要分裂
        root = splitTreeNode(root);
        // 返回树的根节点
        while(root.parent != null){
            root = root.parent;
        }
        return root;
    }

    // 分裂出左节点
    public void copyKey(BTreeNode srcNode, BTreeNode dstNode, int start, int end){
        //System.arraycopy(srcNode.data, start, dstNode.data, 0, end - start + 1);
        for(int i = start; i <= end; i++){
            dstNode.data.add(srcNode.data.get(i));
        }
    }

    // 分裂出右节点
    public void copyPoint(BTreeNode srcNode, BTreeNode dstNode, int start, int end){
        //System.arraycopy(srcNode.point, start, dstNode.point, 0, end - start + 1);
        if(srcNode.point.size() < 1)
            return;
        for(int i = start; i <= end; i++){
            dstNode.point.add(srcNode.point.get(i));
        }
    }

    // 合并到父节点
    public void mergePoint(int index, BTreeNode leftNode, BTreeNode rightNode, BTreeNode parentNode){
        parentNode.point.add(index, leftNode);
        parentNode.point.add(index + 1, rightNode);
    }

    // B树删除K操作
//    1、叶子节点上，如果删除后节点key数量大于等于1,直接删除操作结束
//    2、叶子节点上，如果删除后节点key数量等于0,需要从父节点借元素，兄弟节点的元素移到父节点中
//    如果兄弟节点的key数量被借后等于0，则需要合并节点，减少分支树
//    3、如果在非叶子节点上，则将后继填充到删除位置，然后重复1,2删除后继
    public BTreeNode delete(BTreeNode root, Object t){
        BTreeNode tempRoot = root;
        BTreeNode targetNode = search(tempRoot, t);
        if(targetNode == null){// 不存在K
            return root;
        }
        if(root == targetNode && targetNode.data.size() == 1 && targetNode.point.size() == 0){// 只有一个值了
            targetNode.data.remove(t);
            return root;
        }
        // 非叶子节点，删除后继节点，删除后继节点等于删除叶子节点
        BTreeNode successor = null;
        if(targetNode.point.size() != 0) {
            successor = successor(root, t);
            // 交换值
            if (successor != null) {
                // 交换值
                Object tempData = successor.data.get(0);
                successor.data.set(0, t);
                int index = 0;
                for (int i = 0; i < targetNode.data.size(); i++){
                    if(targetNode.data.get(i).equals(t)){
                        index = i;
                        break;
                    }
                }
                targetNode.data.set(index, tempData);
                targetNode = successor;
                //t = tempData;
            }
        }// 转换为删除叶子节点上的数据
        //else{// 删除叶子节点上的数据
        {    // 直接删除|借位|合并
            if(targetNode.data.size() > 1){
                // 可直接删除
                targetNode.data.remove(t);
            }else{
                // 借位：把借的数据移到父节点，父节点下沉一个数据到待删除节点
                BTreeNode renderNode = null;
                if((renderNode = renderBrotherNode(targetNode, "left")) != null){
                    // 借左节点中的数据，借最后一个
                    Object renderData = renderNode.data.get(renderNode.data.size() - 1);
                    // 父节点借位data的下标
                    int index = 0;
                    for(int i= 0; i < renderNode.parent.point.size(); i++){
                        if(renderNode.parent.point.get(i) == renderNode){
                            index = i;
                        }
                    }
                    // 父节点数据下沉到待删除节点
                    targetNode.data.set(0, renderNode.parent.data.get(index));
                    // 借位数据上移到父节点
                    renderNode.parent.data.set(index, renderData);
                    // 删除借位节点的数据
                    renderNode.data.remove(renderNode.data.size() - 1);
                }else if((renderNode = renderBrotherNode(targetNode, "right")) != null){
                    // 借右节点中的数据，借第一个
                    Object renderData = renderNode.data.get(0);

                    // 父节点借位data的下标
                    int index = 0;
                    for(int i= 0; i < renderNode.parent.point.size(); i++){
                        if(renderNode.parent.point.get(i) == renderNode){
                            index = i - 1;
                        }
                    }
                    // 父节点数据下沉到待删除节点
                    targetNode.data.set(0, renderNode.parent.data.get(index));
                    // 借位数据上移到父节点
                    renderNode.parent.data.set(index, renderData);
                    // 删除借位节点的数据
                    renderNode.data.remove(0);
                }  else{// 左右节点和父节点的数据都为1，合并数据。如果从父节点借数据也是必合并，因为原本的指向删除节点的point对应的data变为了空

                    // 指向待删除节点的指针
                    int index = 0;
                    for(int i= 0; i < targetNode.parent.point.size(); i++){
                        if(targetNode.parent.point.get(i) == targetNode){
                            index = i;// 指向待删除节点的指针
                        }
                    }
                    // 待删除节点的父节点
                    BTreeNode parentNode = targetNode.parent;
                    if(index + 1 == targetNode.parent.point.size()){
                        // 向左合并
                        targetNode.parent.point.get(index - 1).data.add(targetNode.parent.data.get(index - 1));
                        // 移除多余的值和指针
                        targetNode.parent.data.remove(index - 1);
                        targetNode.parent.point.remove(index);
                    }else{
                        // 默认向右合并
                        targetNode.parent.point.get(index + 1).data.add(0, targetNode.parent.data.get(index));
                        // 移除多余的值和指针
                        targetNode.parent.data.remove(index);
                        targetNode.parent.point.remove(index);
                    }

                    // 需要向上合并
                    while(parentNode.data.size() == 0){
                        // 根节点
                        // if(parentNode.parent == null || parentNode.parent.data.size() == 0){
                        if(parentNode.parent == null){
                            root = parentNode.point.get(0);
                            root.parent = null;
                            break;
                        }

                        index = 0;
                        for(int i= 0; i < parentNode.parent.point.size(); i++){
                            if(parentNode.parent.point.get(i) == parentNode){
                                index = i;// 指向待删除节点的指针
                            }
                        }
                        BTreeNode newNode = new BTreeNode(m);
                        newNode.data.addAll(parentNode.point.get(0).data);
                        newNode.point.addAll(parentNode.point.get(0).point);

                        BTreeNode mergeNode = null;
                        if(index + 1 == parentNode.parent.point.size() && index != 0){
                            parentNode.parent.point.get(index - 1).data.add(parentNode.parent.data.get(index - 1));
                            newNode.parent = parentNode.parent.point.get(index - 1);

                            parentNode.parent.data.remove(index - 1);
                            parentNode.parent.point.remove(index);
                            parentNode.parent.point.get(index - 1).point.add(newNode);
                            mergeNode = parentNode.parent.point.get(index - 1);
                        }else{
                            parentNode.parent.point.get(index + 1).data.add(0, parentNode.parent.data.get(index));
                            newNode.parent = parentNode.parent.point.get(index + 1);

                            parentNode.parent.data.remove(index);
                            parentNode.parent.point.remove(index);
                            parentNode.parent.point.get(index).point.add(0, newNode);
                            mergeNode = parentNode.parent.point.get(index);
                        }
                        // 修改父结点指针
                        for (int i = 0; i < newNode.point.size(); i++){
                            newNode.point.get(i).parent = newNode;
                        }
                        // 检查合并后的节点是否需要向上分裂
                        // 父节点下沉，再合并上去不会出现分裂的情况，因此不用一直往上检查
                        splitTreeNode(mergeNode);
                        parentNode = parentNode.parent;
                    }
                }
            }
        }
        return root;
    }


    // 分裂节点
    public BTreeNode splitTreeNode(BTreeNode root){
        int index = 0;
        while(root.data.size() >= m) {
            // 分裂点数据
            index = root.data.size() / 2;
            Object splitData = root.data.get(index);
            // 节点分裂
            BTreeNode leftNode = new BTreeNode(m);
            BTreeNode rightNode = new BTreeNode(m);
            copyKey(root, leftNode, 0, index - 1);
            copyPoint(root, leftNode, 0, index);
            copyKey(root, rightNode, index + 1, root.data.size() - 1);
            copyPoint(root, rightNode, index + 1, root.point.size() - 1);
            if (root.parent == null) {// 分裂成新的父节点，树高度增加
                BTreeNode parentNode2 = new BTreeNode(m);
                parentNode2.data.add(splitData);
                leftNode.parent = parentNode2;
                rightNode.parent = parentNode2;
                // 原本子节点的父节点指向新的分裂节点
                for (int i = 0; i < leftNode.point.size(); i++) {
                    leftNode.point.get(i).parent = leftNode;
                }
                for (int i = 0; i < rightNode.point.size(); i++) {
                    rightNode.point.get(i).parent = rightNode;
                }
                // 合并分裂节点到父节点
                mergePoint(0, leftNode, rightNode, parentNode2);
                root = parentNode2;
            } else {// 已有父节点，直接插入
                // 确定在父节点中的插入位置
                index = 0;
                for (int i = 0; i < root.parent.data.size(); i++) {
                    if (((Comparable) splitData).compareTo(root.parent.data.get(i)) > 0) {
                        index = i + 1;
                    }
                }
                root.parent.data.add(index, splitData);
                // 父节点原本指向当前节点的指针去掉
                int prePoint = 0;
                for (int i = 0; i < root.parent.point.size(); i++) {
                    if (root.parent.point.get(i) == root) {
                        prePoint = i;
                        break;
                    }
                }
                root.parent.point.remove(prePoint);
                // 原本子节点的父节点指向新的分裂节点
                for (int i = 0; i < leftNode.point.size(); i++) {
                    leftNode.point.get(i).parent = leftNode;
                }
                for (int i = 0; i < rightNode.point.size(); i++) {
                    rightNode.point.get(i).parent = rightNode;
                }
                leftNode.parent = root.parent;
                rightNode.parent = root.parent;
                // 合并分裂节点到父节点
                mergePoint(index, leftNode, rightNode, root.parent);
            }
            // 向上检查，检查父节点是否满足分裂条件
            if (root.parent == null) {
                return root;
                //break;
            } else {
                root = root.parent;
            }
        }
        return root;
    }

    // 能否从兄弟节点借数据。如果可以，返回兄弟节点
    public BTreeNode renderBrotherNode(BTreeNode root, String type){
        // 没有父节点
        BTreeNode parent = root.parent;
        if(parent == null){
            return null;
        }
        int i = 0;
        while(i < parent.point.size()){
            if(root.parent.point.get(i) == root){
                break;
            }
            i++;
        }
        if(i >= parent.point.size()){
            return null;
        }
        BTreeNode brotherNode = null;
        switch (type){
            case "left":{
                if(i == 0)return null;
                brotherNode = parent.point.get(i - 1);
            }break;
            case "right":{
                if(i + 1 >= parent.point.size()){
                    return null;
                }
                brotherNode = parent.point.get(i + 1);
            }break;
            default: return null;
        }
        if(brotherNode != null && brotherNode.data.size() > 1){
            return brotherNode;
        }
        return null;
    }

    // 查找某个数据，并返回所在的节点
    public BTreeNode search(BTreeNode root, Object t){
        while(root != null){
            int i = 0;
            boolean flag = true;
            for(i = 0; i < root.data.size(); i++){
                if(((Comparable)t).compareTo(root.data.get(i)) == 0){// 存在
                    return root;
                }else if(((Comparable)t).compareTo(root.data.get(i)) < 0){// 当前值大于t
                    if(root.point.size() > i){
                        root = root.point.get(i);
                        flag = false;
                        break;
                    }else{
                        return null;
                    }
                }else{// 当前值小于t
                    continue;
                }
            }
            if(flag && i == root.data.size()){
                if(root.point.size() - 1 == i){
                    root = root.point.get(i);
                }else if(root.point.size() < i){
                    return null;
                }
            }
        }
        return null;
    }

    // 查找K的前驱节点
    // 如果存在前驱节点，前驱K一定是节点中的最后一个K
    public BTreeNode precursor(BTreeNode root, Object k){
        return null;
    }

    // 查找K的后继节点
    // 如果存在后继节点，后继K一定是节点中的第一个K。或者只存在一个节点时，后继为顺序节点
    public BTreeNode successor(BTreeNode root, Object k){
        BTreeNode tempRoot = root;
        BTreeNode node = new BTree<>().search(tempRoot, k);
        if(k == null){
            return null;
        }
        int i = 0;
        while(i < node.data.size()){
            if(k.equals(node.data.get(i))){
                i++;
                break;
            }
            i++;
        }
        // 非单节点，但是单节点应该不会在这里出现
        if(node.point.size() != 0){
            node= node.point.get(i);
            while(node.point.size() != 0){
                node= node.point.get(0);
            }
        }
        return node;
    }

    // 随机生成数据添加与删除测试
    public static Map<String, List<Integer>> generateRandomData(int len){

        HashMap<String, List<Integer>> result = new HashMap<>();
        List<Integer> insert = new ArrayList<>(len);
        List<Integer> delete = new ArrayList<>(len);

        List<Integer> data = new ArrayList<>(len);
        List<Integer> data2 = new ArrayList<>(len);
        int tempLen = len;
        while (tempLen > 0){
            data.add(tempLen);
            data2.add(tempLen);
            tempLen--;
        }
        int index = 0;
        while (tempLen < len){
            index = new Random().nextInt(data.size());
            insert.add(data.get(index));
            data.remove(index);
            tempLen++;
        }
        while (tempLen > 0){
            index = new Random().nextInt(data2.size());
            delete.add(data2.get(index));
            data2.remove(index);
            tempLen--;
        }

        result.put("insert", insert);
        result.put("delete", delete);

        return result;
    }

    public static void main(String[] args){

        // Integer[] data = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
        // Integer[] data = new Integer[]{39, 22, 97, 41, 53, 13, 21, 40, 30, 27, 33, 36, 35, 34, 24, 29, 26, 17, 28, 29, 31, 32};
        Integer[] data = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17};
        // Integer[] data = new Integer[]{10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 71, 72};
        // Integer[] data = new Integer[]{39, 22, 97, 41, 53, 13, 21, 40, 30, 27, 33, 36, 35, 34, 24, 29, 26};

        // 创建B-树
        //BTreeNode root = new BTree<Integer>().init(data);

        //BTreeNode node = new BTree<Integer>().search(root, 33);
        //BTreeNode successorNode = new BTree<>().successor(root, 28);
        // BTreeNode root2 = new BTree<>().delete(root, 12);

        // 删除叶节点数据-Integer[] data = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
//        root = new BTree<>().delete(root, 11);
//        root = new BTree<>().delete(root, 10);
//        root = new BTree<>().delete(root, 9);
//        root = new BTree<>().delete(root, 8);
//        root = new BTree<>().delete(root, 7);
//        root = new BTree<>().delete(root, 6);
//        root = new BTree<>().delete(root, 5);
//        root = new BTree<>().delete(root, 4);
//        root = new BTree<>().delete(root, 3);
//        root = new BTree<>().delete(root, 2);
//        root = new BTree<>().delete(root, 1);

        // 删除非叶子节点数据
//        root = new BTree<>().delete(root, 8);
//        root = new BTree<>().delete(root, 4);
//        root = new BTree<>().delete(root, 9);
//        root = new BTree<>().delete(root, 2);

        // 删除非叶子节点数据-Integer[] data = new Integer[]{10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 71, 72};
//        root = new BTree<>().delete(root, 20);
//        root = new BTree<>().delete(root, 71);
//        root = new BTree<>().delete(root, 60);
//        root = new BTree<>().delete(root, 80);
//        root = new BTree<>().delete(root, 100);


/*        for (int j = 0; j < 10000; j++) {
            // 随机序列删除测试
            Map<String, List<Integer>> testData = generateRandomData(100);
            //System.out.println("insert: " + testData.get("insert"));
            //System.out.println("delete: " + testData.get("delete"));

//        Integer[] data = new Integer[]{16, 9, 18, 20, 11, 15, 14, 5, 4, 12, 2, 6, 19, 1, 10, 7, 8, 3, 13, 17};
//        Integer[] delete = new Integer[]{18, 11, 20, 14, 1, 19, 4, 17, 3, 5, 9, 7, 10, 16, 2, 12, 13, 15, 6, 8};
            Integer[] data = testData.get("insert").toArray(new Integer[]{});
            // 创建B-树
            BTreeNode root = new BTree<Integer>().init(data);
            for (int i = 0; i < testData.get("delete").size(); i++){
                //System.out.println("i=" + i);
                root = new BTree<>().delete(root, testData.get("delete").get(i));
            }
        }*/
//        for (int i = 0; i < delete.length; i++){
//            root = new BTree<>().delete(root, delete[i]);
//        }
        BTreeNode root = new BTree<Integer>().init(data);
        root = new BTree<>().delete(root, 11);

        System.out.println("end");
    }
}
